/// 大整数算术运算实现

///| 绝对值加法（两个正数相加）
pub fn add_abs(self : BigInt, other : BigInt) -> BigInt {
  let max_len = if self.digits.length() > other.digits.length() {
    self.digits.length()
  } else {
    other.digits.length()
  }
  
  let result = Array::make(max_len + 1, 0U)
  let mut carry : UInt64 = 0
  
  for i = 0; i < max_len; i = i + 1 {
    let a = if i < self.digits.length() { self.digits[i].to_uint64() } else { 0 }
    let b = if i < other.digits.length() { other.digits[i].to_uint64() } else { 0 }
    
    let sum = a + b + carry
    result[i] = (sum & 0xFFFFFFFF).to_uint()
    carry = sum >> 32
  }
  
  if carry > 0 {
    result[max_len] = carry.to_uint()
  }
  
  { digits: result, negative: false }.normalize()
}

///| 绝对值减法（假设self >= other）
pub fn sub_abs(self : BigInt, other : BigInt) -> BigInt {
  let   result = Array::make(self.digits.length(), 0U)
  let mut borrow : Int64 = 0
  
  for i = 0; i < self.digits.length(); i = i + 1 {
    let a = self.digits[i].to_int64()
    let b = if i < other.digits.length() { other.digits[i].to_int64() } else { 0 }
    
    let diff = a - b - borrow
    if diff < 0 {
      result[i] = (diff + 0x100000000).to_int().reinterpret_as_uint()
      borrow = 1
    } else {
      result[i] = diff.to_int().reinterpret_as_uint()
      borrow = 0
    }
  }
  
  { digits: result, negative: false }.normalize()
}

pub impl Eq for BigInt with op_equal(self : BigInt, other : BigInt) -> Bool {
  
    if self.negative != other.negative {
      return false
    }
    
    if self.digits.length() != other.digits.length() {
      return false
    }
    
    for i = 0; i < self.digits.length(); i = i + 1 {
      if self.digits[i] != other.digits[i] {
        return false
      }
    }
    
    true
  }


///| 加法运算
pub impl Add for BigInt with op_add(self : BigInt, other : BigInt) -> BigInt {
  if self.is_zero() {
    return other
  }
  if other.is_zero() {
    return self
  }
  
  if self.negative == other.negative {
    // 同号相加
    let result = self.add_abs(other)
    { digits: result.digits, negative: self.negative }
  } else {
    // 异号相加，转换为减法
    let cmp = self.compare_abs(other)
    if cmp == 0 {
      return BigInt::zero()
    } else if cmp > 0 {
      let result = self.sub_abs(other)
      { digits: result.digits, negative: self.negative }
    } else {
      let result = other.sub_abs(self)
      { digits: result.digits, negative: other.negative }
    }
  }
}

///| 减法运算
pub impl Sub for BigInt with op_sub(self : BigInt, other : BigInt) -> BigInt {
  self + other.negate()
}

///| 乘法运算（基础版本）
pub impl Mul for BigInt with op_mul(self : BigInt, other : BigInt) -> BigInt {
  if self.is_zero() || other.is_zero() {
    return BigInt::zero()
  }
  
  let result_len = self.digits.length() + other.digits.length()
  let  result = Array::make(result_len, 0U)
  
  for i = 0; i < self.digits.length(); i = i + 1 {
    let mut carry : UInt64 = 0
    for j = 0; j < other.digits.length(); j = j + 1 {
      let prod = self.digits[i].to_uint64() * other.digits[j].to_uint64() + 
                 result[i + j].to_uint64() + carry
      result[i + j] = (prod & 0xFFFFFFFF).to_uint()
      carry = prod >> 32
    }
    
    if carry > 0 {
      result[i + other.digits.length()] = carry.to_uint()
    }
  }
  
  let negative = self.negative != other.negative
  { digits: result, negative }.normalize()
}

///| 除法和求余运算
pub fn div_mod(self : BigInt, other : BigInt) -> (BigInt, BigInt) {
  if other.is_zero() {
    abort("Division by zero")
  }
  
  if self.is_zero() {
    return (BigInt::zero(), BigInt::zero())
  }
  
  let self_abs = self.abs()
  let other_abs = other.abs()
  
  let cmp = self_abs.compare_abs(other_abs)
  if cmp < 0 {
    return (BigInt::zero(), self)
  } else if cmp == 0 {
    let quotient = if self.negative == other.negative { BigInt::one() } else { BigInt::one().negate() }
    return (quotient, BigInt::zero())
  }
  
  // 长除法实现
  let (quotient, remainder) = self_abs.long_division(other_abs)
  
  let final_quotient = if self.negative == other.negative {
    quotient
  } else {
    quotient.negate()
  }
  
  let final_remainder = if self.negative {
    remainder.negate()
  } else {
    remainder
  }
  
  (final_quotient, final_remainder)
}

///| 长除法实现
fn long_division(self : BigInt, divisor : BigInt) -> (BigInt, BigInt) {
  let mut quotient = BigInt::zero()
  let mut remainder = BigInt::zero()

  // 从最高位开始处理
  for i = self.digits.length() - 1; i >= 0; i = i - 1 {
    // 将当前位添加到余数
    remainder = (remainder << 32) +
      BigInt::from_int(self.digits[i].reinterpret_as_int())

    // 计算当前位的商
    let mut digit_quotient = 0
    while remainder.compare_abs(divisor) >= 0 {
      remainder = remainder - divisor
      digit_quotient = digit_quotient + 1
    }

    // 将商的当前位添加到结果
    quotient = (quotient << 32) +
      BigInt::from_int(digit_quotient)
  }
  (quotient.normalize(), remainder.normalize())
}

///| 除法运算
pub impl Div for BigInt with op_div(self : BigInt, other : BigInt) -> BigInt {
  let (quotient, _) = self.div_mod(other)
  quotient
}

///| 求余运算
pub impl Mod for BigInt with op_mod(self : BigInt, other : BigInt) -> BigInt {
  let (_, remainder) = self.div_mod(other)
  remainder
}

///| 左移运算（相当于乘以2^n）
pub impl Shl for BigInt with op_shl(self : BigInt, n : Int) -> BigInt {
  if n <= 0 || self.is_zero() {
    return self
  }
  
  let word_shift = n / 32
  let bit_shift = n % 32
  
  let new_len = self.digits.length() + word_shift + (if bit_shift > 0 { 1 } else { 0 })
  let  result = Array::make(new_len, 0U)
  
  // 字移位
  for i = 0; i < self.digits.length(); i = i + 1 {
    result[i + word_shift] = self.digits[i]
  }
  
  // 位移位
  if bit_shift > 0 {
    let mut carry : UInt = 0
    for i = word_shift; i < new_len - 1; i = i + 1 {
      let val = result[i].to_uint64()
      result[i] = ((val << bit_shift) | carry.to_uint64()).to_uint()
      carry = (val >> (32 - bit_shift)).to_uint()
    }
    if carry > 0 {
      result[new_len - 1] = carry
    }
  }
  
  { digits: result, negative: self.negative }.normalize()
}

/// 右移运算（相当于除以2^n）
pub impl Shr for BigInt with op_shr(self : BigInt, n : Int) -> BigInt {
  if n <= 0 || self.is_zero() {
    return self
  }
  let word_shift = n / 32
  let bit_shift = n % 32
  if word_shift >= self.digits.length() {
    return BigInt::zero()
  }
  let new_len = self.digits.length() - word_shift
  let result = Array::make(new_len, 0U)

  // 字移位
  for i = 0; i < new_len; i = i + 1 {
    result[i] = self.digits[i + word_shift]
  }

  // 位移位
  if bit_shift > 0 {
    let mut carry : UInt = 0
    for i = new_len - 1; i >= 0; i = i - 1 {
      let val = result[i].to_uint64()
      result[i] = ((val >> bit_shift) | (carry.to_uint64() << (32 - bit_shift))).to_uint()
      carry = (val & ((1 << bit_shift) - 1)).to_uint()
    }
  }
  { digits: result, negative: self.negative }.normalize()
}